package com.kaesar.leetcode.LeetCode_051_100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeetCode_080 {
    public static int removeDuplicates(int[] nums) {
        // 如果数组的长度不大于2，则不可能出现元素出现超过两次的情况，直接返回
        if (nums.length == 1 || nums.length == 2) {
            return nums.length;
        }
        // 已经出现过2次的数字
        List<Integer> twiceNums = new ArrayList<>();
        Set<Integer> onceNums = new HashSet<>();
        onceNums.add(nums[0]);
        int result = nums.length;
        for (int i = 1; i < result; ) {
            if (twiceNums.contains(nums[i])) {
                // 出现过2次的，直接移到最后一位非2次的位置
                for (int j = i + 1; j < result; j++) {
                    swap(nums, j - 1, j);
                }
                result--;
                continue;
            }
            if (onceNums.contains(nums[i])) {
                // 出现过一次的，添加到twiceNums中
                twiceNums.add(nums[i]);
            } else {
                // 第一次出现的，添加到onceNums中
                onceNums.add(nums[i]);
            }
            i++;
        }
        return result;
    }

    public static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3};
        System.out.println(removeDuplicates(nums));
    }
}
